package labuladong.第一章.二叉搜索树;

import leetcode.day_2020_12_14_12_21.TreeNode;

// 判断二叉搜索树
public class CheckBST {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }

    public boolean isValidBST2(TreeNode root) {
        return isBst(root, null, null);
    }

    public boolean isBst(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) {
            return true;
        }
        if (min!=null && min.val >= root.val) {
            return false;
        }
        if (max!=null && max.val <= root.val) {
            return false;
        }
        return isBst(root.left, min, root) && isBst(root.right, root, max);
    }
}
